<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>
<body>
    <script>
        // //定义链表
        // function LinkList(){
        //     //定义一个节点类
        //     var Node=function(data){
        //         this.data = data; //节点数据
        //         this.next = null; //节点指向
        //     }
        //     var length = 0; //长度
        //     var head = null;//头节点
        //     var tail = null;//尾节点

        //     //添加一个新节点 在尾部添加
        //     this.append=function(data){
        //         var node = new Node(data);
        //         if(!head){
        //             head = node;
        //             tail = node;
        //         }else{
        //             tail.next = node; //尾节点指向新创建的节点
        //             tail=node;  //tail指向新添加的节点
        //         }
        //         length +=1;    //长度+1
        //         return true;
        //     };
        //     //打印链表
        //     this.print=function(){
        //         var curr_node = head;
        //         var str= "";
        //         while(curr_node){
        //             str += curr_node.data.toString()+"->";
        //             curr_node = curr_node.next;
        //         }
        //         str += "null";
        //         console.log(str);
        //         console.log(`长度为${length.toString()}`)
        //     };
        //     //在链表指定位置添加节点
        //     this.insert=function (index,data){
        //         //当不符合要求时候返回false
        //         if(index<0||index>length){
        //             return false
        //         }else if(index == length){ //插入位置等于链表长度时候
        //             return this.append(data);
        //         }else{
        //             var new_node = new Node(data);
        //             //插入位置等于0时候，换头术
        //             if(index == 0){
        //                 new_node.next = head;
        //                 head = new_node;
        //             }else{
        //                 //大于0时候小于链表长度时候，我们只需要知道你要插入的位置前一个节点就可以
        //                 var insert_index=1;
        //                 var curr_node=head;
        //                 //找到应该插入的位置
        //                 while(insert_index < index){      
        //                     curr_node=curr_node.next;
        //                     insert_index ++;
        //                 }
        //                 //这里就是插入位置前一个节点next指向插入节点 插入节点next指向插入位置前一个节点的next
        //                 var next_node=curr_node.next;
        //                 curr_node.next=new_node;
        //                 new_node.next=next_node;
        //             }
        //             length +=1;
        //             return true;
        //         }
        //     };
        //     //在链表指定位置删除节点
        //     this.remove=function (index){
        //         //当不符合要求时候返回false
        //         if(index<0||index>=length){
        //             return false
        //         }else{
        //             var del_node = null;
        //             //删除位置等于0时候，换头术
        //             if(index == 0){
        //                 del_node = head;
        //                 head = head.next;
        //             }else{
        //                 //大于0时候小于等于链表长度时候，我们只需要知道你要删除的位置前一个节点就可以
        //                 var insert_index=1;
        //                 var curr_node=head;
        //                 //找到应该删除的位置
        //                 while(insert_index < index){      
        //                     curr_node=curr_node.next;
        //                     insert_index ++;
        //                 }
        //                 del_node = curr_node.next;
        //                 //删除的位置前一个节点的next等于删除节点的后一个节点
        //                 curr_node.next=curr_node.next.next;                       
        //                 if(curr_node.next == null){
        //                     tail=curr_node;
        //                 }     
        //             }
        //             length -=1;
        //             return del_node.data;
        //         }
        //     };
        //     //返回指定位置节点的值
        //     this.get=function(index){
        //         if(index<0 || index >=length){
        //             return null;
        //         }

        //         var node_index=0;
        //         var curr_node=head;
        //         while(node_index < index){
        //             node_index ++;
        //             curr_node = curr_node.next;
        //         }
        //         return curr_node.data;
        //     };
        //     //返回指定元素索引
        //     this.indexOf=function(data){
        //         var index = -1;
        //         var curr_node=head;
        //         while(curr_node){
        //             index ++;
        //             if(curr_node.data == data){
        //                 return index;
        //             }else{
        //                 curr_node=curr_node.next;
        //             }
        //         }
        //         return -1;
        //     };
        //     // isEmpty
        //     this.isEmpty = function(){
        //         return length == 0;
        //     };
        //     // 清空链表
        //     this.clear = function(){
        //         head = null;
        //         tail = null;
        //         length = 0;
        //     };
        //     // 返回链表头节点的值
        //     this.head = function(){
        //         return this.get(0);
        //     };
        //     // 返回链表尾节点的值
        //     this.tail = function(){
        //         return this.get(length-1);
        //     };
        //     //返回链表大小
        //     this.length = function(){
        //         return length;
        //     };
        // }
        // var a=new LinkList();


        // var Node = function(data){
        //     this.data = data;
        //     this.next = null;
        // }
        // var node1 = new Node(1);
        // var node2 = new Node(2);
        // var node3 = new Node(3);
        // var node4 = new Node(4);
        // var node5 = new Node(5);
        // node1.next = node2;
        // node2.next = node3;
        // node3.next = node4;
        // node4.next = node5;
        // function print(node){
        //     var curr_node = node;
        //     while(curr_node){
        //         console.log(curr_node.data);
        //         curr_node = curr_node.next;
        //     }
        // };
        // print(node1)
        // // 迭代翻转
        // function reverse_iter(head){
        //     if(!head){
        //         return null;
        //     }
        //     var pre_node = null;  //当前节点的前一个节点
        //     var curr_node = head;//当前要翻转的节点
        //     while(curr_node){
        //         var next_node = curr_node.next;//当前节点的后一个节点
        //         curr_node.next=pre_node;// 对当前节点进⾏行行翻转
        //         pre_node = curr_node;// pre_node向后滑动
        //         curr_node=next_node; // curr_node向后滑动
        //     }
        //     //最后要返回pre_node,当循环结束时,pre_node指向翻转前链表的最后⼀一个节点
        //     return pre_node;     
        // };
        
        // // 递归翻转
        // //递归的思想，精髓之处在于甩锅，你做不到的事情让别人去做，等别人做完了，你在别人的基础上去做
        // function reverse_iter(head){
        //     if(!head){
        //         return null;
        //     }
        //     if(head.next == null){
        //         return head
        //     }
        //     //从下一节点开始进行翻转
        //     var new_head=reverse_iter(head.next);
        //     //把当前节点连接到链表上
        //     head.next.next=head; 
        //     head.next=null;
        //     return new_head;
        // }


        //合并两个有序链表
        var Node = function(data){
        this.data = data;
        this.next = null;
        }
        var node1 = new Node(1);
        var node2 = new Node(4);
        var node3 = new Node(9);
        var node4 = new Node(2);
        var node5 = new Node(5);
        var node6 = new Node(6);
        var node7 = new Node(10);
        node1.next = node2;
        node2.next = node3;

        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        function merge_link(head1, head2){
            if(head1 == null){
                return head2;
            }else if(head2 == null){
                return head2;
            }

            var merge_head=null;// 合并后链表头
            var merge_tail=null;// 合并后链表尾
            var curr_1=head1;
            var curr_2=head2;
            while(curr_1 && curr_2){
                // 找到最小值
                var min_curr;
                if(curr_1.data>curr_2.data){
                    min_curr = curr_2;
                    curr_2 = curr_2.next;
                }else{
                    min_curr = curr_1;
                    curr_1 = curr_1.next;
                }

                if(merge_head == null){
                    merge_head = new Node(min_curr.data);
                    merge_tail =merge_head;
                }else{
                    //把最小值链接到链表尾部
                    merge_tail.next = min_curr;
                    merge_tail = min_curr;   
                }
            }
            // 链表可能还有⼀一部分没有合并进来
            var rest_link =null;
            if(curr_1){
                rest_link = curr_1;
            }else if(curr_2){
                rest_link = curr_2;
            }
            merge_tail.next = rest_link;
            while(rest_link){
                merge_tail = rest_link;
                rest_link = rest_link.next;  
            }
            console.log(merge_tail);
            return merge_head;
        };
        console.log(merge_link(node1, node4));
    </script>
</body>
</html>